public class MagicFinder {

	public static void main(String[] args) {
		MagicFinder finder = new MagicFinder();
		int[] a = new int[] { -1, 0, 1, 2, 3, 6 };
		System.out.println(finder.findMagic(a));
	}

	public int findMagic(int[] a) {
		return findMagic(a, 0, a.length);
	}

	private int findMagic(int[] a, int h, int t) {
		if (h > t)
			return -1;
		int idx = (h + t) / 2;
		int m = a[idx];

		if (m == idx)
			return m;
		else if (m > idx)
			return findMagic(a, h, idx - 1);
		else
			return findMagic(a, idx + 1, t);
	}

}
